package at.tasat.util;

import java.util.Iterator;

public class IntList implements Iterable<Integer> {
	private final Node head;
	private final Node tail;
	private int size;

	public IntList() {
		head = new Node(0);
		tail = new Node(0);
		clear();
	}

	public Node add(int index, int value) {
		assert 0 <= index && index <= size;
		Node nodeToInsert = new Node(value);
		Node node = getNode(index);
		Node nextNode = node.next;
		connect(node, nodeToInsert);
		connect(nodeToInsert, nextNode);
		size++;
		return nodeToInsert;
	}

	private static void connect(Node n1, Node n2) {
		n1.next = n2;
		n2.prev = n1;
	}

	public void clear() {
		connect(head, tail);
		size = 0;
	}

	public Node get(int index) {
		assert 0 <= index && index < size;
		return getNode(index + 1);
	}

	private Node getNode(int index) {
		Node node;
		if (index < size() / 2) {
			node = head;
			while(index > 0) {
				node = node.next;
				index--;
			}
		} else {
			node = tail;
			index = size() + 1 - index;
			while(index > 0) {
				node = node.prev;
				index--;
			}
		}
		return node;
	}

	public void remove(int index) {
		remove(get(index));
	}

	public void remove(Node node) {
		connect(node.prev, node.next);
		node.prev = null;
		node.next = null;
		size--;
	}

	public int size() {
		return size;
	}

	@Override
	public Iterator<Integer> iterator() {
		return new IntListIterator(head.next);
	}

	private class IntListIterator implements Iterator<Integer> {
		private Node cursor;

		public IntListIterator(Node cursor) {
			this.cursor = cursor;
		}

		@Override
		public boolean hasNext() {
			return cursor != tail;
		}

		@Override
		public Integer next() {
			Integer result = Integer.valueOf(cursor.getValue());
			cursor = cursor.next;
			return result;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}

	}

	public final class Node {
		private final int value;
		private Node next;
		private Node prev;

		private Node(int value) {
			this.value = value;
		}

		public int getValue() {
			return value;
		}
	}
}
